import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 先建图，统计入度和邻接表
        //    邻接表实现使用哈希表
        Map<Integer, List<Integer>> edges = new HashMap<>();
        int[] in = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){
            // a -> b
            int b = prerequisites[i][0];
            int a = prerequisites[i][1];
            if(!edges.containsKey(a)){
                edges.put(a, new ArrayList<Integer>());
            }
            // 统计 a 的邻接表
            edges.get(a).add(b);
            in[b]++;
        }

        // 2. 将入度为0的元素都添加到队列中
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0){
                queue.offer(i);
            }
        }

        // 3. 取出入度为0的元素，遍历该元素的邻接表，消除边 bfs
        //    将入度为0的元素添加到队列中
        while(!queue.isEmpty()){
            int t = queue.poll();
            for(int i : edges.getOrDefault(t, new ArrayList<Integer>())){
                in[i]--;
                if(in[i] == 0){
                    queue.offer(i);
                }
            }
        }

        // 4. 判断是否有环
        for(int i = 0; i < numCourses; i++){
            if(in[i] > 0){
                return false;
            }
        }
        return true;
    }
}